﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;
using System.Linq;

namespace Grafos {
    /// <summary>
    /// Especialização de Grafo, representa um grafo com arestas ponderadas
    /// </summary>
    public class GrafoPonderado : Grafo {

        /// <summary>
        /// Conjunto de arestas ponderadas do grafo
        /// </summary>
        protected new HashSet<ArestaPonderada> Arestas { get; set; }


        /// <summary>
        /// Instancia um novo grafo ponderado, com um conjunto vazio de vértices e arestas
        /// </summary>
        public GrafoPonderado() {
            Arestas = new HashSet<ArestaPonderada>();
            Vértices = new Dictionary<string, Vértice>();
        }

        /// <summary>
        /// Diz quantas arestas há no grafo
        /// </summary>
        public override int QuantidadeArestas {
            get {
                return Arestas.Count;
            }
        }

        /// <summary>
        /// Calcula o peso total de todas as arestas do grafo
        /// </summary>
        /// <returns>O valor dos pesos somados</returns>
        /// <remarks>
        /// Para minimizar este valor, utilize um algoritmo de Minimum Spanning Tree (Kruskal ou Prim)
        /// </remarks>
        /// <example>
        /// <code>
        /// GrafoPonderado g = new GrafoPonderado();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta("A", "B", 10);
        /// g.AdicionarAresta("A", "C", 15);
        /// g.AdicionarAresta("B", "C", 12);
        /// float peso = g.PesoTotal(); // 10+15+12 = 27
        /// </code>
        /// </example>
        public float PesoTotal() {
            float w = 0;
            foreach (ArestaPonderada a in Arestas)
                w += a.W;
            return w;
        }

        /// <summary>
        /// Adiciona uma nova aresta ponderada ao grafo
        /// </summary>
        /// <param name="a">Uma aresta ponderada a ser adicionada</param>
        /// <exception cref="ArgumentException">A deve ser uma aresta ponderada</exception>
        /// <see cref="Grafo.AdicionarAresta(Aresta)"/>
        public override void AdicionarAresta(Aresta a) {
            if (!(a is ArestaPonderada))
                throw new ArgumentException("Um grafo ponderado tem somente arestas ponderadas");
            AdicionarAresta((ArestaPonderada)a);
        }

        /// <summary>
        /// Adiciona uma nova aresta ponderada ao grafo
        /// </summary>
        /// <param name="a">Aresta a ser adicionada</param>
        /// <see cref="Grafo.AdicionarAresta(Aresta)"/>
        public virtual void AdicionarAresta(ArestaPonderada a) {
            Arestas.Add(a);
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo, a partir de dois vértices
        /// </summary>
        /// <param name="v1">Uma das extremidades da aresta</param>
        /// <param name="v2">Uma das extremidades da aresta</param>
        /// <see cref="Grafo.AdicionarAresta(Vértice, Vértice)"/>
        public override void AdicionarAresta(Vértice v1, Vértice v2) {
            Arestas.Add(new ArestaPonderada(v1, v2));
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo, a partir de dois vétices, com determinado valor
        /// </summary>
        /// <param name="v1">Uma das extremidades da aresta</param>
        /// <param name="v2">Uma das extremidades da aresta</param>
        /// <param name="valor">Valor de peso da aresta</param>
        /// <see cref="Grafo.AdicionarAresta(Vértice, Vértice)"/>
        public virtual void AdicionarAresta(Vértice v1, Vértice v2, float valor) {
            Arestas.Add(new ArestaPonderada(v1, v2, valor));
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo, a partir do nome de dois vértices
        /// </summary>
        /// <param name="v1">Nome de uma das extremidades da aresta</param>
        /// <param name="v2">Nome de uma das extremidades da aresta</param>
        /// <see cref="Grafo.AdicionarAresta(string, string)"/>
        public override void AdicionarAresta(string v1, string v2) {
            Arestas.Add(new ArestaPonderada(BuscarVértice(v1), BuscarVértice(v2)));
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo, a partir do nome de dois vértices
        /// </summary>
        /// <param name="v1">Nome de uma das extremidades da aresta</param>
        /// <param name="v2">Nome de uma das extremidades da aresta</param>
        /// <param name="valor">Valor de peso da aresta</param>
        /// <see cref="Grafo.AdicionarAresta(string, string)"/>
        public virtual void AdicionarAresta(string v1, string v2, float valor) {
            Arestas.Add(new ArestaPonderada(BuscarVértice(v1), BuscarVértice(v2), valor));
        }

        /// <summary>
        /// Diz se há no grafo uma aresta paralela
        /// </summary>
        /// <param name="a">Aresta a ser verificada</param>
        /// <returns>True caso haja uma aresta paralela</returns>
        /// <remarks>
        /// Atalho para mandar um dos vértices da aresta procurar uma aresta até o outro
        /// É necessário que haja uma aresta paralela a A, mas DIFERENTE DE A, no grafo
        /// </remarks>
        /// <exception cref="ArgumentException">A não pertence ao grafo ou não é ponderada</exception>
        /// <see cref="Grafo.PossuiArestaParalela(Aresta)"/>
        public override bool PossuiArestaParalela(Aresta a) {
            if (!(a is ArestaPonderada))
                throw new ArgumentException("A não é aresta ponderada");
            if (!Arestas.Contains(a))
                throw new ArgumentException("A não está no grafo");
            return a.Extremidade1.ProcurarArestas(a.Extremidade2).Count > 1;
        }

        /// <summary>
        /// Diz se o grafo possui pelo menos um loop
        /// </summary>
        /// <returns>True caso haja algum loop no grafo, false caso contrário</returns>
        /// <example>
        /// Com loop:
        /// <code>
        /// GrafoPonderado g = new GrafoPonderado();
        /// g.AdicionarVértice("A", "B", 2);
        /// g.AdicionarAresta("A", "A", 3);
        /// g.PossuiLoop(); // true
        /// </code>
        /// Sem loop:
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B");
        /// g.AdicionarAresta("A", "B", 2);
        /// g.AdicionarAresta("B", "A", 4);
        /// g.AdicionarAresta("A", "B", 1);
        /// g.PossuiLoop(); // false
        /// g.PossuiCiclo(); // true
        /// </code>
        /// </example>
        public override bool PossuiLoop() {
            foreach (ArestaPonderada a in Arestas) {
                if (a.ÉLoop)
                    return true;
            }
            return false;
        }

        /// <summary>
        /// Realiza uma busca em largura no grafo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="restante">Grafo restante da busca, ou seja, a parte do grafo desconexa ao ponto de partida</param>
        /// <param name="encontrouCiclo">Diz se a pesquisa encontrou algum ciclo ao gerar a árvore</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <remarks>
        /// Se o grafo for desconexo, o parâmetro por referência "restante" possui a parte desconexa da árvore gerada
        /// O parâmetro encontrouCiclo não garante que o grafo não há ciclos, somente que o componente conexo que a árvore engloba não há ciclos
        /// Ou seja, para validar existência ou não de ciclos, é necessário aplicar Buscas em Largura até que o restante seja vazio
        /// A busca em largura desconsidera o peso das arestas. Se este comportamento não é desejado, utilizar o Algoritmo de Djikstra
        /// </remarks>
        /// <exception cref="ArgumentException">Caso o vértice de partida (raíz) não pertença ao grafo</exception>
        /// <example>
        /// <code>
        /// GrafoPonderado g = new GrafoPonderado();
        /// Grafo resto;
        /// bool teveCiclo;
        /// g.AdicionarVértice("A", "B", "C", "D");
        /// g.AdicionarAresta("A", "B", 10);
        /// g.AdicionarAresta("A", "C", 5);
        /// g.AdicionarAresta("B, "D", 7);
        /// g.AdicionarAresta("B", "C", 9);
        /// g.AdicionarAresta("C", "D", 1);
        /// Árvore a = g.BuscaEmLargura(g.BuscarVértice("A"), out resto, out teveCiclo);
        /// // resto = grafo vazio
        /// // teveCiclo = true
        /// // a = (A-B, A-C, B-D) ou (A-B, A-C, C-D)
        /// </code>
        /// </example>
        public override Árvore BuscaEmLargura(Vértice partida, out Grafo restante, out bool encontrouCiclo) {
            if (!Vértices.ContainsValue(partida))
                throw new ArgumentException("Vértice de partida da busca não pertence ao grafo");

            Vértice u;
            GrafoPonderado g = (GrafoPonderado)this.Cópia();
            restante = new Grafo();
            Queue<Vértice> Q = new Queue<Vértice>();
            List<Vértice> rest = new List<Vértice>(), vertArvore = new List<Vértice>(), vizinhança;
            const int branco = 0, cinza = 1, preto = 2;
            int i;

            encontrouCiclo = false;

            foreach (Vértice v in g.Vértices.Values) {
                v.Tag = branco;
                v.λ = float.PositiveInfinity;
                v.π = null;
                rest.Add(v);
            }
            partida = g.BuscarVértice(partida.Nome);
            partida.Tag = cinza;
            partida.λ = 0;
            partida.π = null;
            Q.Enqueue(partida);

            while (Q.Count > 0) {
                u = Q.Dequeue();
                rest.Remove(u);
                vertArvore.Add(u);
                vizinhança = u.Vizinhança();
                foreach (Vértice v in vizinhança) {
                    if ((int)v.Tag == branco) {
                        v.Tag = cinza;
                        v.λ = u.λ + 1;
                        v.π = u;
                        Q.Enqueue(v);
                    } else if ((int)v.Tag == cinza) {
                        encontrouCiclo = true;
                    }
                }
                u.Tag = preto;
            }

            for (i = 0; i < rest.Count; i++) {
                restante.AdicionarVértice(new Vértice(rest[i].Nome));
            }

            foreach (Aresta a in g.Arestas) {
                if ((int)a.Extremidade1.Tag == branco) {
                    restante.AdicionarAresta(restante.BuscarVértice(a.Extremidade1.Nome), restante.BuscarVértice(a.Extremidade2.Nome));
                }
            }

            return Árvore.GerarDePredecessores(vertArvore, false);
        }

        /// <summary>
        /// Realiza uma busca em largura no grafo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <remarks>
        /// Se o grafo for desconexo, o parâmetro por referência "restante" possui a parte desconexa da árvore gerada
        /// O parâmetro encontrouCiclo não garante que o grafo não há ciclos, somente que o componente conexo que a árvore engloba não há ciclos
        /// Ou seja, para validar existência ou não de ciclos, é necessário aplicar Buscas em Largura até que o restante seja vazio
        /// A busca em largura desconsidera o peso das arestas. Se este comportamento não é desejado, utilizar o Algoritmo de Djikstra
        /// </remarks>
        /// <exception cref="ArgumentException">Caso o vértice de partida (raíz) não pertença ao grafo</exception>
        public override Árvore BuscaEmLargura(Vértice partida) {
            Grafo resto;
            bool ciclo;
            return BuscaEmLargura(partida, out resto, out ciclo);
        }

        /// <summary>
        /// Realiza uma busca em largura no grafo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="ciclos">Diz se a pesquisa encontrou algum ciclo ao gerar a árvore</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <remarks>
        /// Se o grafo for desconexo, o parâmetro por referência "restante" possui a parte desconexa da árvore gerada
        /// O parâmetro encontrouCiclo não garante que o grafo não há ciclos, somente que o componente conexo que a árvore engloba não há ciclos
        /// Ou seja, para validar existência ou não de ciclos, é necessário aplicar Buscas em Largura até que o restante seja vazio
        /// A busca em largura desconsidera o peso das arestas. Se este comportamento não é desejado, utilizar o Algoritmo de Djikstra
        /// </remarks>
        /// <exception cref="ArgumentException">Caso o vértice de partida (raíz) não pertença ao grafo</exception>
        public override Árvore BuscaEmLargura(Vértice partida, out bool ciclos) {
            Grafo resto;
            return BuscaEmLargura(partida, out resto, out ciclos);
        }

        /// <summary>
        /// Realiza uma busca em largura no grafo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="resto">Grafo restante da busca, ou seja, a parte do grafo desconexa ao ponto de partida</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <remarks>
        /// Se o grafo for desconexo, o parâmetro por referência "restante" possui a parte desconexa da árvore gerada
        /// O parâmetro encontrouCiclo não garante que o grafo não há ciclos, somente que o componente conexo que a árvore engloba não há ciclos
        /// Ou seja, para validar existência ou não de ciclos, é necessário aplicar Buscas em Largura até que o restante seja vazio
        /// A busca em largura desconsidera o peso das arestas. Se este comportamento não é desejado, utilizar o Algoritmo de Djikstra
        /// </remarks>
        /// <exception cref="ArgumentException">Caso o vértice de partida (raíz) não pertença ao grafo</exception>
        public override Árvore BuscaEmLargura(Vértice partida, out Grafo resto) {
            bool ciclo;
            return BuscaEmLargura(partida, out resto, out ciclo);
        }

        /// <summary>
        /// Cria uma cópia do grafo, copiando todos os vértices e arestas
        /// </summary>
        /// <returns>Um grafo idêntico a este, mas com ponteiros diferentes (duplicação de memória)</returns>
        /// <remarks>
        /// A cópia é profunda. Nenhum trecho de memória é compartilhado
        /// </remarks>
        /// <see cref="Grafo.Cópia"/>
        public override Grafo Cópia() {
            GrafoPonderado g = new GrafoPonderado();

            foreach (Vértice v in Vértices.Values) {
                Vértice novo = new Vértice(v.Nome);
                novo.Lambda = v.Lambda;
                novo.Pi = v.Pi;
                novo.Tag = v.Tag;
                g.AdicionarVértice(novo);
            }

            foreach (Vértice v in g.Vértices.Values) {
                if (v.Pi != null)
                    v.Pi = g.Vértices[v.Pi.Nome];
            }

            foreach (ArestaPonderada a in Arestas) {
                ArestaPonderada nova = new ArestaPonderada(a.Nome, g.Vértices[a.Extremidade1.Nome], g.Vértices[a.Extremidade2.Nome], a.Valor);
                g.AdicionarAresta(nova);
            }


            return g;
        }

        /// <summary>
        /// Algoritmo de Kruskal para encontrar Minimum Spanning Tree
        /// </summary>
        /// <returns>Uma árvore que seja Minimum Spanning Tree deste grafo</returns>
        /// <example>
        /// <code>
        /// GrafoPonderado g = new GrafoPonderado();
        /// nomes = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
        /// matriz = new float[,] {
        ///     {0, 12, 0, 10, 0, 0, 0, 0, 0, 0},
        ///     {12, 0, 5, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 5, 0, 7, 4, 0, 0, 0, 0, 0},
        ///     {10, 0, 7, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 0, 4, 0, 0, 12, 3, 1, 0, 0},
        ///     {0, 0, 0, 0, 12, 0, 12, 0, 0, 0},
        ///     {0, 0, 0, 0, 3, 12, 0, 0, 0, 0},
        ///     {0, 0, 0, 0, 1, 0, 0, 0, 6, 3},
        ///     {0, 0, 0, 0, 0, 0, 0, 6, 0, 4},
        ///     {0, 0, 0, 0, 0, 0, 0, 3, 4, 0}
        /// };
        /// g = GrafoPonderado.GerarDeMatrizDeAdjacencia(nomes, matriz);
        /// ÁrvorePonderada a = g.Kruskal();
        /// 
        /// </code>
        /// </example>
        public ÁrvorePonderada Kruskal() {
            ÁrvorePonderada a = new ÁrvorePonderada();
            GrafoPonderado g = (GrafoPonderado)this.Cópia();
            int set = 0, tag;

            foreach (Vértice v in g.Vértices.Values) {
                v.Tag = set++; // cada vértice é colocado em um set diferente
                a.AdicionarVértice(v); // coloca o vértice na árvore
            }

            // "sort edges into nondecreasing order, according to w"
            List<ArestaPonderada> arestas = g.Arestas.ToList();
            arestas.Sort(new ComparadorLambda());

            foreach (ArestaPonderada e in arestas) {
                if ((int)e.Extremidade1.Tag != (int)e.Extremidade2.Tag) {
                    // unir sets
                    tag = (int)e.Extremidade2.Tag;
                    foreach (Vértice v in g.Vértices.Values) {
                        if ((int)v.Tag == tag)
                            v.Tag = e.Extremidade1.Tag;
                    }
                    // criar a aresta na árvore
                    a.AdicionarAresta(e.Extremidade1, e.Extremidade2, e.Valor);
                }
            }

            return a;
        }

        /// <summary>
        /// Algoritmo de Djikstra para encontrar a árvore de caminhos mínimos a partir de um determinado ponto
        /// </summary>
        /// <param name="raíz">Ponto que deve ter todos os caminhos minimos relacionados</param>
        /// <returns>Uma árvore de caminhos mínimos a partir da raíz dada</returns>
        /// <exception cref="ArgumentException">Raíz não pertence ao grafo</exception>
        /// <example>
        /// <code>
        /// GrafoPonderado g;
        /// string[] nomes;
        /// float[,] matriz;
        /// nomes = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
        /// matriz = new float[,] {
        ///     {0, 12, 0, 10, 0, 0, 0, 0, 0, 0},
        ///     {12, 0, 5, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 5, 0, 7, 4, 0, 0, 0, 0, 0},
        ///     {10, 0, 7, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 0, 4, 0, 0, 12, 3, 1, 0, 0},
        ///     {0, 0, 0, 0, 12, 0, 12, 0, 0, 0},
        ///     {0, 0, 0, 0, 3, 12, 0, 0, 0, 0},
        ///     {0, 0, 0, 0, 1, 0, 0, 0, 6, 3},
        ///     {0, 0, 0, 0, 0, 0, 0, 6, 0, 4},
        ///     {0, 0, 0, 0, 0, 0, 0, 3, 4, 0}
        /// };
        /// 
        /// ÁrvorePonderada ap = g.Djikstra(g.BuscarVértice("E"));
        /// // ap é a árvore formada pelos vértices: A-B, B-C, C-D, C-E, E-F, E-G, E-H, H-I, H-J
        /// </code>
        /// </example>
        /// <remarks>Utiliza a função Djikstra(Vértice[])</remarks>
        /// <seealso cref="Djikstra(Vértice[])"/>
        public ÁrvorePonderada Djikstra(Vértice raíz) {
            return Djikstra(new Vértice[] { raíz });
        }

        /// <summary>
        /// Algoritmo de Djikstra para encontrar a árvore de caminhos mínimos a partir de vários pontos
        /// </summary>
        /// <param name="raízes">Pontos que "disputam" regiões</param>
        /// <returns>Uma árvore de caminhos mínimos a partir da raíz dada, desconexo de acordo com as raízes</returns>
        /// <exception cref="ArgumentException">Uma das raízes não pertence ao grafo</exception>
        /// <remarks>
        /// Apesar de retornar uma "ÁrvorePonderada", o grafo retornado não é uma árvore, pois há grupos desconexos
        /// Na verdade, são representandas N árvores no grafo retornado, onde N é o número de raízes
        /// </remarks>
        /// <example>
        /// <code>
        /// GrafoPonderado g;
        /// string[] nomes;
        /// float[,] matriz;
        /// nomes = new string[] { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
        /// matriz = new float[,] {
        ///     {0, 12, 0, 10, 0, 0, 0, 0, 0, 0},
        ///     {12, 0, 5, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 5, 0, 7, 4, 0, 0, 0, 0, 0},
        ///     {10, 0, 7, 0, 0, 0, 0, 0, 0, 0},
        ///     {0, 0, 4, 0, 0, 12, 3, 1, 0, 0},
        ///     {0, 0, 0, 0, 12, 0, 12, 0, 0, 0},
        ///     {0, 0, 0, 0, 3, 12, 0, 0, 0, 0},
        ///     {0, 0, 0, 0, 1, 0, 0, 0, 6, 3},
        ///     {0, 0, 0, 0, 0, 0, 0, 6, 0, 4},
        ///     {0, 0, 0, 0, 0, 0, 0, 3, 4, 0}
        /// };
        /// 
        /// ÁrvorePonderada ap = g.Djikstra(new Vértice[] { g.BuscarVértice("A"), g.BuscarVértice("E"), g.BuscarVértice("J") });
        /// // as seguintes arestas estarão presentes em ap: A-D, B-C, C-E, E-F, E-G, E-H, I-J
        /// </code>
        /// </example>
        public ÁrvorePonderada Djikstra(Vértice[] raízes) {
            foreach (Vértice v in raízes) {
                if (!Vértices.ContainsKey(v.Nome))
                    throw new ArgumentException("A raíz " + v.Nome + " não pertence ao grafo");
            }

            GrafoPonderado g;
            FilaDePrioridadesVértice Q = new FilaDePrioridadesVértice();
            Vértice u;
            float w;
            int i;
            List<Vértice> vizinhança;

            g = (GrafoPonderado)this.Cópia();

            // atualiza raízes
            for (i = 0; i < raízes.Length; i++) {
                raízes[i] = g.BuscarVértice(raízes[i].Nome);
            }

            // inicializa vértices
            foreach (Vértice v in g.Vértices.Values) {
                v.λ = float.PositiveInfinity;
                v.π = null;
                Q.Add(v);
            }

            // começa pelas raízes
            foreach (Vértice v in raízes) {
                v.λ = 0;
            }

            // Djisktra
            while (Q.Count > 0) {
                u = Q.ExtrairMenor();
                vizinhança = u.Vizinhança();
                foreach (Vértice v in vizinhança) {
                    if (Q.Contains(v)) {
                        // relaxamento
                        w = ((ArestaPonderada)v.ProcurarAresta(u)).W;
                        if (v.λ > u.λ + w) {
                            v.λ = u.λ + w;
                            v.π = u;
                        }
                    }
                }
            }


            return ÁrvorePonderada.GerarDePredecessores(g.Vértices.Values, false);
        }

        /// <summary>
        /// Gera um grafo completo, a partir dos vértices presentes neste grafo
        /// </summary>
        /// <returns>Um grafo Kn, onde N é o número de vértices deste grafo</returns>
        /// <remarks>
        /// O grafo original não é alterado
        /// O peso de uma aresta criada será +Infinito
        /// </remarks>
        public override Grafo GerarKN() {
            GrafoPonderado g = new GrafoPonderado();

            foreach (Vértice v in Vértices.Values) {
                Vértice novo = new Vértice(v.Nome);
                novo.Lambda = v.Lambda;
                novo.Pi = v.Pi;
                novo.Tag = v.Tag;
                g.AdicionarVértice(novo);
            }

            foreach (Vértice v in g.Vértices.Values) {
                foreach (Vértice v2 in g.Vértices.Values) {
                    // v != v2 e não há aresta entre v e v2 ainda
                    if ((!v.Equals(v2)) && v.ProcurarAresta(v2) == null) {
                        ArestaPonderada a = (ArestaPonderada)this.BuscarVértice(v.Nome).ProcurarAresta(this.BuscarVértice(v2.Nome));
                        g.AdicionarAresta(v, v2, a == null ? float.PositiveInfinity : a.Valor);
                    }
                }
            }

            return g;
        }

        /// <summary>
        /// Busca pelo passeio determinado pela heurística de Vizinho Mais Próximo
        /// </summary>
        /// <param name="inicio">Vértice de início da busca</param>
        /// <returns>Um passeio completo pelo grafo</returns>
        /// <remarks>
        /// Saindo do vértice de início, procura-se sempre pelo vértice mais próximo que não esteja no passeio
        /// Começa e termina pelo vértice de início
        /// </remarks>
        public Passeio NearestNeighbour(Vértice inicio) {
            Passeio p;
            List<Vértice> n;
            Vértice maisPróximo;
            int i;
            float menorDist;

            if (!Vértices.ContainsValue(inicio))
                throw new ArgumentException("Vértice não pertence ao grafo");

            p = new Passeio();

            p.AdicionarVértice(inicio);

            while (p.QuantidadeVértices < Vértices.Count) {
                n = p.ÚltimoVértice.Vizinhança();

                maisPróximo = null;
                menorDist = float.PositiveInfinity;

                for (i = 0; i < n.Count; i++) {
                    if (!p.Possui(n[i]) && (((ArestaPonderada)p.ÚltimoVértice.ProcurarAresta(n[i])).Valor < menorDist || menorDist == float.PositiveInfinity)) {
                        maisPróximo = n[i];
                        menorDist = ((ArestaPonderada)p.ÚltimoVértice.ProcurarAresta(n[i])).Valor;
                    }
                }

                p.AdicionarVértice(maisPróximo);
            }

            p.AdicionarVértice(inicio);

            return p;
        }

        /// <summary>
        /// Realiza o algoritmo 2-Otimal no grafo ponderado, com a dada inicialização
        /// </summary>
        /// <param name="inicialização">Caminho inicial da inicialização</param>
        /// <returns>Um novo caminho otimizado</returns>
        /// <remarks>
        /// Não altera o valor de inicialização passado
        /// </remarks>
        /// <seealso cref="Passeio.Torcer(int,int)"/>
        public Passeio KOpt2(Passeio inicialização) {
            Passeio c;
            int i, j, n;
            float wi, wj;
            Vértice[] atual;

            c = (Passeio)inicialização.Clone();
            atual = c.Listar();
            n = inicialização.QuantidadeVértices;

            for (i = 0; i < n - 2; i++) {
                for (j = i + 1; j < n - 1; j++) {
                    wi = ((ArestaPonderada)atual[i].ProcurarAresta(atual[i + 1])).Valor;
                    wi += ((ArestaPonderada)atual[j].ProcurarAresta(atual[j + 1])).Valor;
                    wj = ((ArestaPonderada)atual[i].ProcurarAresta(atual[j])).Valor;
                    wj += ((ArestaPonderada)atual[i + 1].ProcurarAresta(atual[j + 1])).Valor;
                    if (wi > wj) {
                        c.Torcer(i + 1, j);
                        atual = c.Listar();
                        i = 0;
                        j = i + 1;
                    }
                }
            }

            return c;
        }


        /// <summary>
        /// Gera uma matriz de adjacência a partir deste grafo
        /// </summary>
        /// <param name="nomes">Lista de nomes dos vértices</param>
        /// <param name="matriz">Matriz de adjacência que indica presença ou não de aresta</param>
        /// <remarks>O grafo é considerado grafo básico simples</remarks>
        /// <example>
        /// <code>
        /// Grafo g;
        /// string[] n;
        /// float[,] m;
        /// 
        /// g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta("A", "A", 5);
        /// g.AdicionarAresta("A", "B", 8);
        /// g.AdicionarAresta("B", "C", 10);
        /// g.GerarMatrizDeAdjacencia(n, m);
        /// // n: "A", "B", "C"
        /// // matriz: { 0, 8, 0,
        /// //           8, 0, 10,
        /// //           0, 10, 0}
        /// </code>
        /// </example>
        public void GerarMatrizDeAdjacencia(out string[] nomes, out float[,] matriz) {
            int i, j;
            int count;
            ArestaPonderada a;

            count = Vértices.Count;
            nomes = new string[count];
            matriz = new float[count, count];

            for (i = 0; i < count; i++) {
                nomes[i] = Vértices.ElementAt(i).Value.Nome;
                for (j = 0; j < count; j++) {
                    if (i != j) {
                        a = (ArestaPonderada)Vértices.ElementAt(i).Value.ProcurarAresta(Vértices.ElementAt(j).Value);
                        matriz[i, j] = (a != null) ? a.Valor : 0;
                    }
                }
            }
        }

        /// <summary>
        /// Gera um grafo ponderado a partir de uma matriz de adjacência
        /// </summary>
        /// <param name="nomes">Nomes dos vértices</param>
        /// <param name="matriz">Matriz de adjacência (somente a parte simétrica inferior é avaliada)</param>
        /// <returns>Um grafo determinado pela matriz de adjacência</returns>
        /// <exception cref="ArgumentException">A quantidade de nomes deve ser igual ao tamanho da matriz, e as duas dimensões da matriz devem ser iguais</exception>
        /// <example>
        /// <code>
        /// string[] nomes = new string[] { "A", "B", "C" };
        /// float[,] matriz = new float[,] {
        ///     { 0, 5, 0},
        ///     { 5, 0, 2},
        ///     { 0, 2, 0}
        /// };
        /// GrafoPonderado g = GrafoPonderado.GerarDeMatrizDeAdjacencia(nomes, matriz);
        /// // g possui os vértices A, B e C, com as arestas A-B (5) e B-C (2)
        /// </code>
        /// </example>
        /// <seealso cref="Grafo.GerarDeMatrizDeAdjacencia"/>
        public static GrafoPonderado GerarDeMatrizDeAdjacencia(string[] nomes, float[,] matriz) {

            if (nomes.Length != matriz.GetLength(0) || nomes.Length != matriz.GetLength(1))
                // transitividade: matriz.GetLength(0) != matriz.getLength(1)
                throw new ArgumentException("Tamanho dos vetores de entrada incorreto");

            int i, j;
            GrafoPonderado g = new GrafoPonderado();

            foreach (string s in nomes) {
                g.AdicionarVértice(new Vértice(s));
            }

            for (j = 1; j < matriz.GetLength(1); j++) {
                for (i = 0; i < j; i++) {
                    if (matriz[i, j] > 0)
                        g.AdicionarAresta(g.BuscarVértice(nomes[i]), g.BuscarVértice(nomes[j]), matriz[i, j]);
                }
            }

            return g;
        }

    }
}
